#include<stdio.h>
#include<stdlib.h>
#include"homework.h"
#define MAX 10
#define ElementType int 
struct Array 
{
    ElementType a[MAX];
    int len;
};  

//将输入数组中的元素挨个输出(从前往后)
void Travel(ElementType *a,int len)
{
    for(int i=0;i<len;i++)
    {
        printf("%d",a[i]);
    }
    printf("\n");
}

// int main()
// {
//     int a[]={1,2,3,4,5};
//     int len=5;
//     Travel(a,len);
// }

//将输入数组中的元素挨个输出(从后往前)
void ReTravel(ElementType *a,int len)
{
    for(int i=len-1;i>=0;i--)
    {
        printf("%d",a[i]);
    }
    printf("\n");
}

// int main()
// {
//     int a[]={1,2,3,4,5};
//     int len=5;
//     ReTravel(a,len);
// }

void InsertTail(struct Array *array,ElementType element)
{
    if(array->len>=MAX)
    {
        printf("out of range!\n");
        return;
    }
    array->a[array->len]=element;
    array->len++;
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertTail(&array,i+1);
//     }
//     Travel(array.a,array.len);
// }

void InsertHead(struct Array *array,ElementType element)
{
    if(array->len>=MAX)
    {
        printf("out of range!\n");
        return;
    }
    for(int i=array->len;i>=0;i--)
    {
        array->a[i]=array->a[i-1];
    }
    array->a[0]=element;
    array->len++;
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertHead(&array,i+1);
//     }
//     Travel(array.a,array.len);
// }

//中间插,给定一个位置和要插入的数,将这个数插入到指定位置
void InsertIndex(struct Array *array,ElementType element,int index)
{
    if(index>=MAX)
    {
        printf("out of range!\n");
        return;
    }
    if(index<0 || index>array->len)
    {
        printf("invalid space!\n");
        return;
    }
    for(int i=array->len;i<index;i--)
    {
        array->a[i]=array->a[i-1];
    }
    array->a[index]=element;
    array->len++;
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertIndex(&array,i+1,1);
//     }
//     Travel(array.a,array.len);
// }

//按位删除
void RemoveIndex(struct Array *array,int index)
{
    if(index>=MAX)
    {
        printf("out of range!\n");
        return;
    }
    if(index<0 ||index>array->len)
    {
        printf("invalid space!\n");
        return;
    }
    for(int i=index;i<array->len;i++)
    {
        array->a[i]=array->a[i+1];
    }
    array->len--;
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertTail(&array,i+1);
//     }
//     RemoveIndex(&array,2);
//     Travel(array.a,array.len);
// }

//按值删除
void RemoveElement(struct Array *array,ElementType element)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==element)
        {
            RemoveIndex(array,i);
            i--;
        }
    }
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertTail(&array,i+1);
//     }
//     Travel(array.a,array.len);
//     RemoveElement(&array,5);
//     Travel(array.a,array.len);
// }

//按位查找
ElementType FindByIndex(struct Array *array,int index)
{
    // if(index>=MAX)
    // {
    //     printf("out of range!\n");
    //     return;
    // }
    if(index<0 || index>=array->len)
    {
        printf("invalid space!\n");
        return 0;
    }
    return array->a[index];
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertTail(&array,i+1);
//     }
//     Travel(array.a,array.len);
//     printf("%d\n",FindByIndex(&array,2));  
// }

int *FindByElement(struct Array *array,ElementType element)
{
    int* findVector=(int *)malloc((array->len+1)*sizeof(ElementType));
    if(findVector==NULL)
    {
        printf("malloc error!\n");
        return 0;
    }
    int count=0;
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==element)
        {
            count++;
            findVector[count]=i;
        }
    }
    findVector[0]=count;
    return findVector;
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertTail(&array,i+1);
//     }
//     Travel(array.a,array.len);
//     int *findVector=FindByElement(&array,6);
//     for(int i=0;i<findVector[0];i++)
//     {
//         printf("%d",findVector[i]);
//     }
//     printf("\n");

//     InsertTail(&array,1);
//     InsertTail(&array,2);
//     InsertTail(&array,2);
//     InsertTail(&array,2);
//     InsertTail(&array,4);
//     Travel(array.a,array.len);

//     int *findVector=FindByElement(&array,2);
//     printf("%d",findVector[0]);
//     printf("\n");
//     printf("%d",array.a[findVector[1]]);
//     printf("\n");
// }

int *FindByElement2(struct Array *array,ElementType element)
{
    int *findVector=(int *)malloc((array->len+1)*sizeof(ElementType));
    if(findVector==NULL)
    {
        printf("malloc error!\n");
        return 0;
    }
    int count=0;
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==element)
        {
            findVector[count]=i;
            count++;
        }
    }
    findVector[count]=-1;
    return findVector;
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     InsertTail(&array,1);
//     InsertTail(&array,2);
//     InsertTail(&array,2);
//     InsertTail(&array,4);
//     InsertTail(&array,2);
//     Travel(array.a,array.len);

//     int *findVector=FindByElement2(&array,2);
//     int *temp=findVector;
//     while(*temp!=-1)
//     {
//         printf("%d ",*temp);
//         temp++;
//     }
//     printf("\n");
//     return 0;
// }

void SetValueByIndex(struct Array *array,ElementType element,int index)
{
    if(index>=MAX)
    {
        printf("out of range!\n");
        return;
    }
    if(index<0 || index>=array->len)
    {
        printf("invalid space!\n");
        return;
    }
    array->a[index]=element;
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertTail(&array,i+1);
//     }
//     Travel(array.a,array.len); 
//     SetValueByIndex(&array,10,2);
//     Travel(array.a,array.len);   
// }

void SetValueByElement(struct Array *array,ElementType old_value,ElementType new_value)
{
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==old_value)
        {
            array->a[i]=new_value;
        }
    }
}

// int main()
// {
//     struct Array array;
//     array.len=0;
//     for(int i=0;i<5;i++)
//     {
//         InsertTail(&array,i+1);
//     }
//     Travel(array.a,array.len); 
//     SetValueByElement(&array,3,9);
//     Travel(array.a,array.len); 
// }

struct Array* FindIntersection(struct Array *array1,struct Array *array2)
{
    struct Array *intersection =(struct Array *)malloc(sizeof(struct Array));
    if(intersection==NULL)
    {
        printf("malloc error!\n");
        return NULL;
    }
    for(int i=0;i<array1->len;i++)
    {
        for(int j=0;j<array2->len;j++)
        {
            if(array1->a[i]==array2->a[j])
            {
                int flag=0;
                for(int k=0;k<intersection->len;k++)
                {
                    if(intersection->a[k]==array1->a[i])
                    {
                        flag=1;
                    }
                }
                if(flag==0)
                {
                    InsertTail(intersection,array1->a[i]);
                }
            }
        }
    }
    return intersection;
}

// int main()
// {
//     struct Array array;
//     struct Array array1;
//     array.len=0;
//     array1.len=0;

//     InsertTail(&array,1);
//     InsertTail(&array,2);
//     InsertTail(&array,2);
//     InsertTail(&array,4);

//     InsertTail(&array1,1);
//     InsertTail(&array1,3);
//     InsertTail(&array1,4);
    
//     Travel(array.a,array.len);
//     Travel(array1.a,array1.len);
//     struct Array *a=FindIntersection(&array,&array1);
//     Travel(a->a,a->len);
//     return 0;
// }

void Depulication(struct Array *array)
{
    fastSort(array->a,0,array->len-1);
    for(int i=0;i<array->len;i++)
    {
        if(array->a[i]==array->a[i+1])
        {
            RemoveIndex(array,i+1);
            i--;
        }
    }
}

struct Array *FindUnionSet(struct Array *array1,struct Array *array2)
{
    struct Array *unionset=(struct Array *)malloc(sizeof(struct Array));
    if(unionset==NULL)
        return NULL;
    for(int i=0;i<array1->len;i++)
    {
        InsertTail(unionset,array1->a[i]);
    }   
    for(int j=0;j<array2->len;j++)
    {
        InsertTail(unionset,array2->a[j]);
    }
    Depulication(unionset);
    return unionset;  
}

// int main()
// {
//     struct Array array;
//     struct Array array1;
//     array.len=0;
//     array1.len=0;

//     InsertTail(&array,1);
//     InsertTail(&array,2);
//     InsertTail(&array,2);
//     InsertTail(&array,4);

//     InsertTail(&array1,1);
//     InsertTail(&array1,3);
//     InsertTail(&array1,4);
    
//     Travel(array.a,array.len);
//     Travel(array1.a,array1.len);
//     struct Array *a=FindUnionSet(&array,&array1);
//     Travel(a->a,a->len);
//     return 0;
// }

struct Array *MergeArray(struct Array *array1,struct Array *array2)
{
    fastSort(array1->a,0,array1->len-1);
    fastSort(array2->a,0,array2->len-1);
    struct Array *Merge=(struct Array *)malloc(sizeof(struct Array));
    Merge->len=0;
    if(Merge==NULL)
        return NULL;
    int i=0,j=0;
    while(i<array1->len && j<array2->len)
    {
        if(array1->a[i]<=array2->a[j])
        {
            InsertTail(Merge,array1->a[i]);
            i++;
        }
        else
        {
            InsertTail(Merge,array2->a[j]);
            j++;
        }
    }
    while(i<array1->len)
    {
        InsertTail(Merge,array1->a[i]);
        i++;
    }
    while(j<array2->len)
    {
        InsertTail(Merge,array2->a[j]);
        j++;
    }
    return Merge;
}

// int main()
// {
//     struct Array array;
//     struct Array array1;
//     array.len=0;
//     array1.len=0;

//     InsertTail(&array,1);
//     InsertTail(&array,4);
//     InsertTail(&array,2);
//     InsertTail(&array,6);

//     InsertTail(&array1,4);
//     InsertTail(&array1,1);
//     InsertTail(&array1,3);
    
//     Travel(array.a,array.len);
//     Travel(array1.a,array1.len);
//     struct Array *a=MergeArray(&array,&array1);
//     Travel(a->a,a->len);
//     return 0;
// }


















